class Solution {
public:
    int numDecodings(string s) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        int n = s.length();
        if (n == 0) {
            return 0;
        }

        vector<int> dp(n);
        if (s[0] >= '1' && s[0] <= '9') {
            dp[0] = 1;
        } else {
            return 0;
        }
        for (int i = 1; i < n; ++i) {
            if (!(s[i] >= '0' && s[i] <= '9')) {
                return 0;
            }
            int val = (s[i - 1] - '0') * 10 + s[i] - '0';
            if (s[i] == '0') {
                if (s[i - 1] != '0' && val >= 1 && val <= 26) {
                    dp[i] = (i - 2 >= 0 ? dp[i - 2] : 1);
                } else {
                    return 0;
                }
            } else {
                dp[i] += dp[i - 1];
                if (s[i - 1] != '0' && val >= 1 && val <= 26) {
                    dp[i] += (i - 2 >= 0 ? dp[i - 2] : 1);
                }
            }
        }
        return dp[n - 1];
    }
};
